#include "Utils.h"
#include "ListNode.h"
#include "TreeNode.h"
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Issue328 {
public:
	ListNode* oddEvenList(ListNode* head) {
		if (head==NULL||head->next==NULL)
			return head;

		ListNode* p=head;
		ListNode* q=head->next;
		ListNode* head1=p;
		ListNode* head2=q;

		while(q!=NULL){
			p->next=q->next;
			p=p->next;
			ListNode* tmp=p;
			p=q;
			q=tmp;
		}

		while(head1->next!=NULL)
			head1=head1->next;

		head1->next=head2;

		return head;
	}
	
	//Better solution
	//ListNode* oddEvenList_Better(ListNode* head) {
	//	if (head != null) {

	//		ListNode odd = head, even = head.next, evenHead = even; 

	//		while (even != null && even.next != null) {
	//			odd.next = odd.next.next; 
	//			even.next = even.next.next; 
	//			odd = odd.next;
	//			even = even.next;
	//		}
	//		odd.next = evenHead; 
	//	}
	//	return head;
	//}
};

int main328(){
	int arr[]={1,2,3,4,5,6,7};
	vector<int> vect(arr,arr+size(arr));
	ListNode* head=createLinkedList(vect);
	printLinkedList(head);

	Issue328 sol;
	head=sol.oddEvenList(head);
	printLinkedList(head);

	return 0;
}